package J.算法.滑动窗口;

import com.sun.javafx.collections.MappingChange;

import java.lang.reflect.MalformedParameterizedTypeException;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

public class _438找到字符串中所有字母异位词 {

    //扩大的时候 判断是不是字母异位 然后valid修改
    //缩小条件 valid = need。size====错啦 应该是长度匹配
    //缩小前进行 结果输出 left存


    public List<Integer> findAnagrams(String s, String p) {

        Map<Character,Integer> window = new HashMap<>();
        Map<Character,Integer> need = new HashMap<>();
        for (char c:p.toCharArray()){
            need.put(c,need.getOrDefault(c,0)+1);
        }

        int left=0,right=0;
        int valid =0;
        List<Integer> res = new LinkedList<>();

        while (right<s.length()){
            char in = s.charAt(right);
            right++;
            if (need.containsKey(in)){
                window.put(in,window.getOrDefault(in,0)+1);
                if (need.get(in).equals(window.get(in))){
                    valid++;
                }
            }

            while (right-left >= p.length()){
                if (valid== need.size()) {
                    res.add(left);
                }

                char out = s.charAt(left);
                left++;

                if (need.containsKey(out)){
                    if (need.get(out).equals(window.get(out))){
                        valid--;
                    }
                    window.put(out,window.getOrDefault(out,1)-1);
                }
            }
        }

        return res;

    }

}
